package main.leetcode.clockin.September;

/**
 * 79. 单词搜索
 *
 * <p>给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * <p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * <p>示例: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]<br>
 * 给定 word = "ABCCED", 返回 true <br>
 * 给定 word = "SEE", 返回 true <br>
 * 给定 word = "ABCB", 返回 false
 *
 * <p>提示：<br>
 * board 和 word 中只包含大写和小写英文字母。 <br>
 * 1 <= board.length <= 200 <br>
 * 1 <= board[i].length <= 200 <br>
 * 1 <= word.length <= 10^3
 */
public class day13 {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        char[] chars = word.toCharArray();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, m, n, i, j, chars, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int m, int n, int i, int j, char[] chars, int index) {
        if (index == chars.length) {
            return true;
        }
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || board[i][j] != chars[index]) {
            return false;
        }
        board[i][j] = '1';
        boolean res =
                dfs(board, m, n, i - 1, j, chars, index + 1)
                        || dfs(board, m, n, i + 1, j, chars, index + 1)
                        || dfs(board, m, n, i, j - 1, chars, index + 1)
                        || dfs(board, m, n, i, j + 1, chars, index + 1);
        board[i][j] = chars[index];
        return res;
    }
}
